package code;

import java.util.Arrays;

public class Code_813 {

    public static void main(String[] a) {

        int[] nums = new int[]{-1,2,-1,3};
        int k = 3;
        double result = largestSumOfAverages(nums,k);
        System.out.println("Code_813.main: " + result);
    }

    public static double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        double[] prefix = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
            System.out.println(prefix[i]);
        }
        double[][] dp = new double[n + 1][k + 1];
        for (int i = 1; i <= n; i++) {
            dp[i][1] = prefix[i] / i;
        }
        for (int j = 2; j <= k; j++) {
            for (int i = j; i <= n; i++) {
                for (int x = j - 1; x < i; x++) {
                    System.out.println("i: "+ i + "  j:  " + j + " dp[i,j]:  " + dp[i][j] + " x: " + x + "  dp[x][j - 1]:  " + (dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x)));
                    dp[i][j] = Math.min(dp[i][j], (dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x)));
                }
            }
        }
        return dp[n][k];
    }
}
